package code.class1;

import cn.hutool.core.util.ArrayUtil;

/**
 * https://leetcode.cn/problems/longest-common-prefix/description/
 * <p>
 * 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，则返回""
 * 示例：
 * 输入: ["flower","flow","flight"]  输出: "fl"
 * 输入: ["dog","racecar","car"] 输出: ""
 */
public class Code02_longestCommonPrefix {

    public static void main(String[] args) {
        String[] str1 = {"flower", "flow", "flight"};
        String[] str2 = {"dog", "racecar", "car"};

        String res1 = longestCommonPrefix(str1);
        System.out.println(ArrayUtil.toString(res1));
        String res = longestCommonPrefix(str2);
        System.out.println(ArrayUtil.toString(res));
    }

    public static String longestCommonPrefix(String[] str) {
        if (str == null || str.length == 0) {
            return "";
        }
        // 先取出比对字符串
        String prefix = str[0];
        // 遍历剩余字符串
        for (int i = 1; i < str.length; i++) {
            // 用每个开头，比较模板字符串
            while (str[i].indexOf(prefix) != 0) {  // 如果当前字符串不以 prefix 开头
                prefix = prefix.substring(0, prefix.length() - 1);  // 缩短公共前缀
                if (prefix.isEmpty()) {
                    return "";  // 如果公共前缀为空，则没有公共前缀
                }
            }
        }
        return prefix;  // 返回最终找到的最长公共前缀
    }


}
